package Algorithm.LRU;

import java.util.HashMap;
import java.util.Map;

public class LRUCacheMine<K,V> {
    private int size;
    private Map<K,DLinkedNode> cache = new HashMap<>();
    private DLinkedNode head;
    private DLinkedNode tail;
    private int capacity;

    class DLinkedNode{
        K key;
        V value;
        DLinkedNode pre;
        DLinkedNode next;
        DLinkedNode(){}
        DLinkedNode(K key, V value){this.key = key;this.value = value;}
    }

    public LRUCacheMine(int capacity){
        this.size = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.pre = head;
    }

    public V get(K key){
        DLinkedNode node = cache.get(key);
        if (null == node){
            return null;
        }

        removeNode(node);
        addToHead(node);

        return node.value;
    }

    public void put(K key, V value){
        DLinkedNode node = cache.get(key);
        if (node == null){
            DLinkedNode newNode = new DLinkedNode(key,value);
            addToHead(newNode);
            size++;
            if (size>capacity){
                removeNode(tail.pre);
                size--;
            }
        }else {
            cache.put(key,node);
            removeNode(node);
            addToHead(node);
        }
    }

    public void removeNode(DLinkedNode node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    public void addToHead(DLinkedNode node){
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }



}
